package main.leetcode.offer.secondround.from03to50;

import main.datastruc.TreeNode;

/** 07.重建二叉树 */
public class ex07 {
    public static void main(String[] args) {
        System.out.println(
                new ex07()
                        .reConstructBinaryTree(
                                new int[] {3, 9, 20, 15, 7}, new int[] {9, 3, 15, 20, 7}));
        System.out.println(
                new ex07()
                        .reConstructBinaryTree(
                                new int[] {1, 2, 4, 7, 3, 5, 6, 8},
                                new int[] {4, 7, 2, 1, 5, 3, 8, 6}));
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        int n = pre.length;
        if (n == 0) {
            return null;
        }
        return build(pre, 0, n - 1, in, 0, n - 1);
    }

    private TreeNode build(int[] pre, int s1, int e1, int[] in, int s2, int e2) {
        if (s1 > e1) {
            return null;
        }
        TreeNode root = new TreeNode(pre[s1]);
        int index = 0;
        for (int i = s2; i <= e2; ++i) {
            if (in[i] == pre[s1]) {
                index = i;
                break;
            }
        }
        root.left = build(pre, s1 + 1, s1 + index - s2, in, s2, index - 1);
        root.right = build(pre, s1 + index - s2 + 1, e1, in, index + 1, e2);
        return root;
    }
}
